// 查找异位词

#include<iostream>
#include<vector>

using namespace std;

class Solution{
public:
    vector<int> findAnagrams(string s, string p){
        int sLen = s.size(), pLen = p.size();
        if (sLen < pLen){
            return vector<int>();
        }
        vector<int> ans;
        // 存储p中的字符
        vector<int> sCount(26);
        vector<int> pCount(26);
        for (int i = 0; i < pLen; i++){
            ++sCount[s[i] - 'a'];
            ++pCount[p[i] - 'a'];
        }

        if (sCount == pCount){
            ans.emplace_back(0);
        }
        // 滑动窗口
        for (int i = 0; i < sLen-pLen; i++){
            // 此处已经开始滑动
            --sCount[s[i] - 'a'];
            ++sCount[s[i + pLen] - 'a'];

            if (sCount == pCount){
                ans.emplace_back(i+1);
            }
        }
        return ans;
    }
    
};


int main(){
    string s = "cbaebabacd";
    string p = "abc";

    Solution solution;

    vector<int> ans = solution.findAnagrams(s, p);

    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] << " ";
    }
    cout << endl;

}
